package com.lql.tree;

/**
 * 线索化二叉树
 */
public class ThreadArrayBinaryTreeDemo {
    public static void main(String[] args) {
        ThreadHeroNode root = new ThreadHeroNode(1, "宋江");
        ThreadHeroNode heroNode1 = new ThreadHeroNode(2, "吴用");
        ThreadHeroNode heroNode2 = new ThreadHeroNode(3, "卢俊义");
        ThreadHeroNode heroNode3 = new ThreadHeroNode(4, "林冲");
        ThreadHeroNode heroNode4 = new ThreadHeroNode(5, "关胜");
        //建立联系
        root.setLeft(heroNode1);
        root.setRight(heroNode2);
        heroNode2.setLeft(heroNode4);
        heroNode2.setRight(heroNode3);
        ThreadListBinaryTree threadListBinaryTree = new ThreadListBinaryTree(root);
        threadListBinaryTree.midOrder();
        System.out.println("__________________");
        //线索化
        threadListBinaryTree.ThreadTree();
        threadListBinaryTree.listThreadTree();


    }
}

class ThreadListBinaryTree {
    //根节点
    private final ThreadHeroNode root;
    private ThreadHeroNode pre = null;//记录前一个结点


    public ThreadListBinaryTree(ThreadHeroNode root) {
        this.root = root;
    }

    /**
     * 中序遍历
     */
    public void midOrder() {
        if (root != null) {
            root.midOrder();
        } else {
            System.out.println("树为空！");
        }
    }

    public void ThreadTree() {
        ThreadTree(root);
    }

    /**
     * 线索化二叉树
     */
    public void ThreadTree(ThreadHeroNode threadHeroNode) {
        if (threadHeroNode == null) {
            System.out.println("树为空，线索化失败！");
            return;
        }
        if (threadHeroNode.getLeft() != null) {
            //左递归线索化
            ThreadTree(threadHeroNode.getLeft());
        }
        //线索化
        if (threadHeroNode.getLeft() == null) {
            threadHeroNode.setLeft(pre);
            threadHeroNode.setLeftType(1);
        }
        if (pre != null && pre.getRight() == null) {
            pre.setRight(threadHeroNode);
            pre.setRightType(1);
        }
        pre = threadHeroNode;
        if (threadHeroNode.getRight() != null) {
            //右递归线索化
            ThreadTree(threadHeroNode.getRight());
        }

    }

    /**
     * 线索化遍历中序线索化二叉树
     */
    public void listThreadTree() {
        ThreadHeroNode threadHeroNode = root;
        while (threadHeroNode != null) {
            while (threadHeroNode.getLeftType() == 0) {
                threadHeroNode = threadHeroNode.getLeft();
            }
            System.out.println(threadHeroNode);
            while (threadHeroNode.getRightType()==1){
                threadHeroNode = threadHeroNode.getRight();
                System.out.println(threadHeroNode);
            }
            threadHeroNode = threadHeroNode.getRight();
        }
    }
}

class ThreadHeroNode {
    private int id;
    private String name;
    private ThreadHeroNode left;//左子树
    private ThreadHeroNode right;//右子树
    private int leftType;//表示左子树的类型，0表示存在左子树，1表示线索化了左子树
    private int rightType;//表示右子树的类型，0表示存在左子树，1表示线索化了左子树

    public ThreadHeroNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public ThreadHeroNode getLeft() {
        return left;
    }

    public void setLeft(ThreadHeroNode left) {
        this.left = left;
    }

    public ThreadHeroNode getRight() {
        return right;
    }

    public void setRight(ThreadHeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    /**
     * 中序遍历
     */
    public void midOrder() {
        if (this.left != null) {
            //左递归
            this.left.midOrder();
        }
        //遍历当前节点
        System.out.println(this);
        if (this.right != null) {
            //右递归
            this.right.midOrder();
        }
    }
}